package com.cqs.leetcode.bit;

/**
 * @author lixiaowen
 * @create 2019-12-26
 */
public class BitMap {

    //要存储元素个数
    private int SIZE;
    //long 占8B=64b 每个long表示64个数
    private long[] words;

    public BitMap(int SIZE) {
        this.SIZE = SIZE;
        //SIZE>>6 为 SIZE/64
        this.words = new long[1 + (this.SIZE >> 6)];
    }

    /**
     * 是否包含数index
     *
     * @param index
     * @return
     */
    public boolean getBit(int index) {
        if (index > SIZE) return false;
        int groupNo = index >> 6;
        int step = index % 64;
        return ((words[groupNo] >> step) & 1) == 1;
    }

    public void setBit(int index) {
        if (index > SIZE) return;
        int groupNo = index >> 6;
        int idx = index % 64;
        //注意这里要写成1L<<idx因为 1<<63 = 1111111111111111111111111111111110000000000000000000000000000000
        //1L<<63=1000000000000000000000000000000000000000000000000000000000000000
        words[groupNo] |= (1L << idx);
    }


    private String toStringWords() {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < words.length; i++) {
            sb.append(Long.toBinaryString(words[i]));
        }
        return sb.toString();
    }

    //1亿
    public static void main(String[] args) {
        int SIZE = 64 * 3;
        BitMap bm = new BitMap(SIZE);
        for (int i = 0; i <= SIZE; i++) {
            boolean exists = bm.getBit(i);
            bm.setBit(i);
            boolean exists2 = bm.getBit(i);
            System.out.println(exists + "\t" + exists2 + "\t" + i + "\t" + bm.toStringWords());
        }
    }
}
